package org.aplombh.java.interview.newcoder;

import java.util.HashMap;

public class NC28_最小覆盖子串 {

    public static void main(String[] args) {
        System.out.println(new NC28_最小覆盖子串().minWindow("XDOYEZODEYXNZ", "XYZ"));
        System.out.println(new NC28_最小覆盖子串_2().minWindow("XDOYEZODEYXNZ", "XYZ"));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow(String S, String T) {
        // write code here
        String res = S;
        boolean flag = false;
        for (int i = 0; i < S.length(); i++) {
            for (int j = i + T.length(); j <= S.length(); j++) {
                String sub = S.substring(i, j);
                if (check(sub, T)) {
                    flag = true;
                    if (sub.length() < res.length()) res = sub;
                }
            }
        }
        if (flag) return res;
        else return "";
    }

    public boolean check(String s, String t) {
        int[] chars = new int[128];
        for (int i = 0; i < s.length(); i++) {
            chars[s.charAt(i)]++;
        }

        for (int i = 0; i < t.length(); i++) {
            if (chars[t.charAt(i)] > 0) chars[t.charAt(i)]--;
            else return false;
        }
        return true;
    }
}


class NC28_最小覆盖子串_2 {

    public String minWindow(String S, String T) {

        int[] hash = new int[128];
        // 将t中所以字符标记为负数，方便check是否合格
        for (int i = 0; i < T.length(); i++)
            hash[T.charAt(i)] -= 1;


        String res = S;
        boolean flag = false;
        for (int l = 0, r = 0; r < S.length(); r++) {
            char rc = S.charAt(r);
            hash[rc]++;

            while (check(hash)) {
                if (res.length() >= r - l + 1) {
                    res = S.substring(l, r + 1);
                    flag = true;
                }
                char lc = S.charAt(l);
                hash[lc]--;
                l++;
            }
        }

        if (flag) return res;
        return "";
    }

    boolean check(int[] hash) {
        for (int j : hash) {
            if (j < 0) return false;
        }
        return true;
    }
}